import {Compare,defaultCompare,ICompareFunction,defaultEquals, IEqualsFunction, } from "../utils";
import LinkedList from "./linked-list";

export default class SortedLinkedList<T> extends LinkedList<T>{
    constructor(
        protected equalsFn: IEqualsFunction<T> = defaultEquals,
        protected compareFn: ICompareFunction<T> = defaultCompare,
    ){
        super(equalsFn);
    }
    push(element:T){
        if(this.isEmpty()){
            super.push(element);
        }else{
            const index = this.getIndexNextSortedElement(element);
            super.insert(element,index);
        }
    }
    /**
     * 插入元素
     * @param element 
     * @param index 排序链表中不能在任意位置插入，但是要使用父类方法，所以给一个默认值
     */
    insert(element:T,index:number=0){
        if(this.isEmpty()){
            return super.insert(element,0);
        }
        index = this.getIndexNextSortedElement(element);
        return super.insert(element,index);
    }

    private getIndexNextSortedElement(element:T):number{
        let current = this.head;
        let i = 0;
        for(;i<this.size()&&current;i++){
            const comp = this.compareFn(element,current.element);
            if(comp === Compare.LESS_THAN){
                return i;
            }
            current = current.next;
        }
        return i;
    }
}